package com.tuling.code;
public class MergeSort {

    public static void main(String[] args) {

    }
    //试用递归方式进行归并排序
    public void process(int [] arry,int left,int right){
        if(left > right){
            return;
        }
        int mid = left + ((right -left)>>1);
        process(arry,left,mid);
        process(arry,mid+1,right);

    }
    //时间复杂度 n*logn
    public void merge(int[] arry,int left,int mid ,int right){
        int[] help = new int[right - left +1];
        //定义三个参数
        int i = 0;
        int p1 = left;
        int p2 = right;
        //归并思想 左半部分和右半部分都不越界
        while (p1 <=mid && p2<= right){
            help[i++] = p1 <= mid ? arry[p1++]:arry[p2++];
        }
        //如果右边越界
        while (p2<=right){
            help[i++] = arry[p2++];
        }
        //右边越界
        while (p1<=mid){
            help[i++] = arry[p1++];
        }
        for (int j = 0; j < help.length; j++) {
            arry[left+j] = help[j];
        }

    }

    //非递归方法实现
    public void mergeSort2(int[] arry){
        if(arry == null || arry.length <2){
            return;
        }
        //
        int N = arry.length;
        int mergeSize = 1;
        //判断是不是步长小于总长度
        while (mergeSize < N){
            int L  = 0;
            while (L < N){
                int mid  = L + mergeSize -1;
                if(mid >N){break;}
                int rigt = Math.min(mid + mergeSize,N);
                merge(arry, L,mid,rigt);
                L = rigt +1;
            }
            //防止int 最大值溢出
            if(mergeSize > N/2){
                break;
            }
            mergeSize >>=1;
        }

    }

    public void merge2(int [] arry,int left,int mid,int right){
        int[] help = new int[right - left +1];
        //定义三个变量指向数组的变化
        int i = 0;
        int p1 = left;
        int p2 = right;
        //当左组和右组都没有越界的时候
        while (p1 <=mid && p2 <= right){
            help[i++] = arry[p1] < arry[p2] ? arry[p1++]:arry[p2++];
        }
        //当有右出现越界
        while (p2 <= right){
            help[i++] = arry[p2++];
        }

        while (p1 <= mid){
            help[i++] = arry[p1++];
        }

        for (int j = 0; j < help.length; j++) {
            help[left+j] = help[j];
        }

    }

    public void mersort2(int [] arry){
        if(arry == null || arry.length <2){
            return;
        }
        int N = arry.length;
        //设置步长
        int mergeSize = 1;
        //步长小于N
        while (mergeSize < N){
            int L = 0;
            while (L <N){
                int M = L + mergeSize;
                if(M > N){break;}
                int right = Math.min(L +mergeSize,N);
                merge(arry,L,M,right);
                L = right+1;
            }
            if(mergeSize > N/2){
                break;
            }
            mergeSize >>=1;

        }

    }

    //最小和问题 拷贝右组 不产生小和  拷贝左组 产生小和 R - p2; 相等的时候先拷贝右组


}
